package LinkedList;

public class _328_OddEvenLinkedList {
    //超出内存与超时
    public ListNode oddEvenList0(ListNode head) {
        if(head==null || head.next==null) return head;
        ListNode oddBegin = new ListNode(Integer.MIN_VALUE);
        ListNode evenBegin = new ListNode(Integer.MIN_VALUE);
        ListNode temp = head;
        ListNode oddp = oddBegin;
        ListNode evenp = evenBegin;
        boolean even = false;
        while(temp!=null){
            if(even){
                evenp.next = temp;
                evenp = evenp.next;
                even = false;
            }else{
                oddp.next = temp;
                oddp = oddp.next;
                even = true;
            }
            temp = temp.next;
        }
        oddp.next = evenBegin.next;
        return oddBegin.next;
    }

    //有参考,odd，even和evenHead实际上为指针，与原有链表无关
    public ListNode oddEvenList(ListNode head) {
        if(head==null) return null;
        ListNode odd = head,even =head.next,evenHead = even;
        while(even!=null && even.next!=null){
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}
